#include <iostream>
#include <chrono> // std::chrono::high_resolution_clock
#include <string> // std::string
#include <fstream> // std::ifstream, std::ofstream
#include <map>
#include <set>
#include <vector>
#include <tuple>
#include <cstdlib>

#include "LNB.h"
#include "k_median.h"


#define	WH_TEST 1
//#define	CHF 1
//#define DEBUG_11 1

void update_file(const std::string f, const std::string c, int id)
{

	std::fstream can(c, std::ios_base::in | std::ios_base::out);
	std::vector<std::tuple<int, int, int, double, double>> buf;
	int a, a_temp;
	int b, b_temp;
	int  ci, c_temp;
	double d, d_temp;
	double e, e_temp;
	if (can.is_open())
	{
		while (can >> a_temp >> b_temp >> c_temp >> d_temp >> e_temp)
		{
			if (a_temp == id)
			{
				a = a_temp; b = b_temp; ci=c_temp; d = d_temp; e = e_temp;
				while (can.get() != '\n');
				continue;
			}
			else
			{
				buf.push_back(std::make_tuple(a_temp, b_temp, c_temp, d_temp, e_temp));
				while (char c = can.get())
				{
					if (c == '\n'|| c == EOF)
						break;
				}
			}
		}
	}
	else
	{
		std::cout << "I can't open c.\n";
		std::cin.get();
		std::exit(1);
	}
	can.close();
	can.open(c, std::ios_base::out | std::ios_base::trunc);
	if(can.is_open())
		for (auto i : buf)
			can << std::get<0>(i) << " " << std::get<1>(i) << " " << std::get<2>(i) << " " << std::get<3>(i) << " " << std::get<4>(i) << std::endl;
	else
	{
		std::cout << "I can't open c.\n";
		std::cin.get();
		std::exit(1);
	}
	can.close();
	std::ofstream fac(f, std::ios_base::out | std::ios_base::app);
	if (!fac.is_open())
	{
		std::cout << "I can't open the fac.\n";
		std::cin.get();
		std::exit(1);
	}
	fac << a + 10000 <<' '<<  b << ' '<< ci << ' '<< d << ' '<< e << std::endl;
	fac.close();
}

void greedy_LNB(wh::facility_info_map& facility_info, wh::candidate_info_map& candidate_info, wh::reference_info_list& refloc_info, wh::Config& config)
{

#ifdef CHF
#define N 20
	std::ifstream chf_temp("F:\\大四课程\\毕业设计\\MILE-RUN-master\\MILE-RUN-00pm\\Debug\\result.txt");
	if (chf_temp.is_open())
	{
		std::cout << "open success.\n";
		std::string  f("F:/大四课程/毕业设计/MILE-RUN-master/datasets/CA_datasets/tmp/800_pos.bak.txt");
		std::string  c("F:/大四课程/毕业设计/MILE-RUN-master/datasets/CA_datasets/tmp/gen_cands_100.txt");
		int temp;
		int tim =0;
		while (chf_temp >> temp && tim <N)
		{
			update_file(f, c, temp);
			while (chf_temp.get() != '\n');
			tim++;
		}
		return 0;
	}
#endif // CHF

	bool is_greedy_k = true;
	// time recorders
	auto begin_time = std::chrono::high_resolution_clock::now();
	auto end_time = std::chrono::high_resolution_clock::now();

	candidate ol_LNB;
	if (is_greedy_k)
	{
#ifdef WH_TEST 
		std::cout << "开始执行 greedy_LNB !\n";
		std::ofstream test_result(config.result_file , std::ios_base::out|std::ios_base::app);
		wh::check_file(test_result, config.result_file);
#endif

		// 构造k贪心算法专用的数据结构
		enum { VS_id, VE_id, VS_dist, VE_dist };
		std::map<int, std::set<std::pair<int, int>>> refloc_LN_map;
		std::map<int, std::pair<int,double>> refloc_info_map;
		int times = 1; // 表示第几次加入新的candidate

		// 打开输出结果文件
		//config.result_file += "LNB.txt";
		//std::ofstream ofs_re(config.result_file); // create results file
		//wh::check_file(ofs_re, config.result_file);

		// 初始化一些数据结构
		begin_time = std::chrono::high_resolution_clock::now();
		typed_directed_graph graph_for_LNB;
		fac_hash_map facs_map;
		LNT_hash_map LNT;
		vertex_nnd_hash_map nnd_map;


		// 加入第一个新设施
		LNB_construct_LNT(!config.is_directed_graph, // this param indicates to convert (true) undirected graph into bidirectional graph or not (false)
			config.edge_file.c_str(),facility_info , refloc_info, LNT, nnd_map, graph_for_LNB, facs_map, refloc_LN_map,refloc_info_map);
		end_time = std::chrono::high_resolution_clock::now();
		//ofs_re << "LNB construct LNT took " << std::chrono::duration_cast<std::chrono::milliseconds>(end_time - begin_time).count() << std::endl;
		test_result << wh::get_dist(refloc_info_map, refloc_info) << std::endl;

		begin_time = std::chrono::high_resolution_clock::now();
		int checked_num;
		//ol_LNB = LNB_query(checked_num, LNT, nnd_map, graph_for_LNB, facs_map, config.candidate_file.c_str(),cands_map);
		ol_LNB = LNB_query(checked_num, LNT, nnd_map, graph_for_LNB, facs_map, candidate_info);
		end_time = std::chrono::high_resolution_clock::now();
		//ofs_re << times << "times " << "LNB took " << std::chrono::duration_cast<std::chrono::milliseconds>(end_time - begin_time).count() << " ms\n"
			   //<< "    check num = " << checked_num << '\n'
			   //<< "    result is c" << ol_LNB.id << ", ERD = " << ol_LNB.ERD << std::endl;
#ifdef WH_TEST
		test_result << ol_LNB.id << "\t" << ol_LNB.ERD << std::endl;
#endif // WH_TEST



		// 加入后面的多个新设施
		++times;
		for (; times <= config.K; times++)
		{
			begin_time = std::chrono::high_resolution_clock::now();
			LNB_update_LNT(ol_LNB, LNT, graph_for_LNB, facs_map, refloc_LN_map, candidate_info, config.refloc_file.c_str(),refloc_info_map);
#ifdef DEBUG_11
		std::cout << "11最近设施是: " << refloc_info_map[11].first << "  最近距离是：" << refloc_info_map[11].second << std::endl;
#endif // DEBUG_2953
			end_time = std::chrono::high_resolution_clock::now();
			//ofs_re << times - 1 << "LNB update LNT took " << std::chrono::duration_cast<std::chrono::milliseconds>(end_time - begin_time).count() << " ms\n";
			test_result << wh::get_dist(refloc_info_map, refloc_info) << std::endl;

			begin_time = std::chrono::high_resolution_clock::now();
			ol_LNB = LNB_query(checked_num, LNT, nnd_map, graph_for_LNB, facs_map, candidate_info);
			//ol_LNB = LNB_query(checked_num, LNT, nnd_map, graph_for_LNB, facs_map, config.candidate_file.c_str(), cands_map);
			end_time = std::chrono::high_resolution_clock::now();
			//ofs_re << times << "times " << "LNB took " << std::chrono::duration_cast<std::chrono::milliseconds>(end_time - begin_time).count() << " ms\n"
				//<< "    check num = " << checked_num << '\n'
				//<< "    result is c" << ol_LNB.id << ", ERD = " << ol_LNB.ERD << std::endl;
#ifdef WH_TEST
			test_result << ol_LNB.id << "\t" << ol_LNB.ERD << std::endl;
#endif // WH_TEST
			if (ol_LNB.ERD <= 0)
				break;
		}
		test_result << std::endl << "最终距离为：\n";
		test_result << wh::get_dist(refloc_info_map, refloc_info) << std::endl;
	}
}

void print_graph(const typed_directed_graph &graph)
{
	std::ofstream out_file("D:\\Experiment\\MILE-RUN\\datasets\\graph.txt", std::ofstream::out | std::ofstream::trunc);
	if (!out_file.fail())
	{
		out_file << "vs ve dist\n---------------\n";
		int edges_count = 0;
		adjacent_edges_hash_map::const_iterator citer_v = graph.adjacent_edges.cbegin();
		for (; citer_v != graph.adjacent_edges.cend(); ++citer_v)
		{
			std::set<out_edge>::const_iterator citer_out_edge = citer_v->second.first.cbegin();
			for (; citer_out_edge != citer_v->second.first.cend(); ++citer_out_edge)
			{
				out_file << citer_v->first.type << citer_v->first.id << ' ' << citer_out_edge->ve.type << citer_out_edge->ve.id << ' ' << citer_out_edge->dist << '\n';
				++edges_count;
			}
		}
		out_file << "---------------\nedges count: " << edges_count << '\n';
		out_file.flush();
	}
}
//--------------------------------------------------------------------------------
// LNB algorithm: construct LNT
// remark: the reference locations file format must be "refloc_id vs_id ve_id dist_vs_refloc dist_refloc_ve prob lon lat"
// [in] is_to_bidirectional: indicate whether to convert (true) undirected graph into bidirectional graph or not (false)
// [in] edges_file_path: file path of edges
// [in] facs_file_path: file path of facilities
// [in] reflocs_file_path: file path of reference locations
// [out] LNT; a hash map as Local Network Table, which needs to be constructed in this function
// [out] nnd_map; a hash map for reference locations that overlap some vertices, which needs to be constructed in this function
// [out] graph: the typed directed graph, which needs to be constructed in this function
// [out] facs_map: a hash map for storing facilities associated with the endpoints, which needs to be constructed in this function
// 参数说明：is_to_bidirectional：指示是否将其转换为有向图
//			 edges_file_path:边文件路径
//			 reflocs_file_path：设施文件路径
//			 LNT：一个被当作Local Network Table的hash表，它将在这个函数中被构造
//			 nnd_map：覆盖了一些顶点的参考位置的hash表，它将在这个函数中被构造
//			 graph:有向图
//			 facs_map：存储设施相关信息的hash表，它将在这个函数中被构造。

void LNB_construct_LNT(bool is_to_bidirectional, const char *edges_file_path, const char *facs_file_path, const char *reflocs_file_path,
					   LNT_hash_map &LNT, vertex_nnd_hash_map &nnd_map, typed_directed_graph &graph, fac_hash_map &facs_map)
{
	// init graph, and deploy facilities
#ifndef ALGO_TESTING_NO_TRACE_GRAPH
	graph.set_testing(&algo_out_file);
#endif
	graph.set_to_bidirectional(is_to_bidirectional);
	graph.init_graph(edges_file_path);

	// deploy facilities and construct related data structure
	graph.deploy_facilities(facs_file_path, &facs_map);

	if (!graph.get_is_facilities_deployed()) // check graph and facilities status
		return;

	// create an extend event visitor for LNB algorithm
	LNB_extend_visitor extend_visitor;
	loc_edges_hash_map refloc_loc_edges_hash_map; // an assistant hash map for local network edges
	extend_visitor.set_data_structure(&facs_map, &refloc_loc_edges_hash_map); // set data structures

	// create a top event visitor for LNB algorithm
	LNB_top_visitor top_visitor;
	top_visitor.set_data_structures(&LNT, &refloc_loc_edges_hash_map, &nnd_map); // set data structures

	// deal with each reference location
	std::ifstream ifs_reflocs(reflocs_file_path); // read reference locations file
	if (ifs_reflocs.is_open()) // reference locations file exists
	{
		char buf[1024];
		while (ifs_reflocs.getline(buf, 1024))
		{
			std::string str_buf(buf);

			// the reference locations file format must be "refloc_id vs_id ve_id dist_vs_refloc dist_refloc_ve prob lon lat"
			std::string::size_type begin_pos = 0, vs_pos, ve_pos, dist_vs_pos, dist_ve_pos, prob_pos, lon_pos;
			vs_pos = str_buf.find(' ', begin_pos);
			ve_pos = str_buf.find(' ', vs_pos + 1);
			dist_vs_pos = str_buf.find(' ', ve_pos + 1);
			dist_ve_pos = str_buf.find(' ', dist_vs_pos + 1);
			prob_pos = str_buf.find(' ', dist_ve_pos + 1);
			lon_pos = str_buf.find(' ', prob_pos + 1);

			int refloc_id = atoi(str_buf.substr(begin_pos, vs_pos - begin_pos).c_str());
			int vs_id = atoi(str_buf.substr(vs_pos + 1, ve_pos - vs_pos - 1).c_str());
			int ve_id = atoi(str_buf.substr(ve_pos + 1, dist_vs_pos - ve_pos - 1).c_str());
			double dist_vs = static_cast<double>(atof(str_buf.substr(dist_vs_pos + 1, dist_ve_pos - dist_vs_pos - 1).c_str()));
			double dist_ve = static_cast<double>(atof(str_buf.substr(dist_ve_pos + 1, prob_pos - dist_ve_pos - 1).c_str()));
			double prob = static_cast<double>(atof(str_buf.substr(prob_pos + 1, lon_pos - prob_pos - 1).c_str()));
			// lon and lat are useless for network traversal

			// insert a reference location vertex to <vs, ve>
			vertex refloc_v(refloc_id, 'r');
			std::vector<directed_edge> removed_edges, inserted_edges;
			graph.insert_vertex(vertex(vs_id, 'v'), vertex(ve_id, 'v'), refloc_v, dist_vs, dist_ve, &removed_edges, &inserted_edges,
				false); // "false" means not to replace overlapped vertex for reference location, we will create a virtual vertex for it

			// traverse graph from the reference location by dijkstra algorithm
			extend_visitor.set_vs_ve(vs_id, ve_id, dist_vs, dist_ve); // the original starting and ending vertices of the reference location
			extend_visitor.set_prob(prob); // set the present probability of the reference location
			refloc_loc_edges_hash_map.clear(); // must reset the assistant hash map for each new reference location
			if (vs_id == ve_id)
				top_visitor.set_overlap(vs_id,refloc_id); // reference location overlaps a vertex
			else
				top_visitor.set_overlap(-1,refloc_id ); // reference location doesn't overlap a vertex
			graph.dijkstra(refloc_v, &top_visitor, &extend_visitor);

			// restore the graph by removing the inserted reference location vertex
			graph.restore_graph(refloc_v, removed_edges, inserted_edges);
		}
	}
}
void LNB_construct_LNT(bool is_to_bidirectional, const char *edges_file_path, const char *facs_file_path, const char *reflocs_file_path, LNT_hash_map &LNT, vertex_nnd_hash_map &nnd_map, typed_directed_graph &graph, fac_hash_map &facs_map, std::map<int, std::set<std::pair<int, int>>> & refloc_LN_map, std::map<int,std::pair<int,double>> & refloc_info_map)
{
	// 对图进行初始化
	graph.set_to_bidirectional(is_to_bidirectional);
	graph.init_graph(edges_file_path);

	// 在图上面部署设施
	graph.deploy_facilities(facs_file_path, &facs_map);

	if (!graph.get_is_facilities_deployed()) // 检查图和设施的状态
		return;

	LNB_extend_visitor extend_visitor;
	loc_edges_hash_map refloc_loc_edges_hash_map; // an assistant hash map for local network edges
	extend_visitor.set_data_structure(&facs_map, &refloc_loc_edges_hash_map); // set data structures

	// create a top event visitor for LNB algorithm
	LNB_k_top_visitor top_visitor;
	top_visitor.set_data_structures(&LNT, &refloc_loc_edges_hash_map, &nnd_map,  &refloc_LN_map,&refloc_info_map); // set data structures

	// deal with each reference location
	std::ifstream ifs_reflocs(reflocs_file_path); // read reference locations file
	if (ifs_reflocs.is_open()) // reference locations file exists
	{
		char buf[1024];
		while (ifs_reflocs.getline(buf, 1024))
		{
			std::string str_buf(buf);

			// the reference locations file format must be "refloc_id vs_id ve_id dist_vs_refloc dist_refloc_ve prob lon lat"
			std::string::size_type begin_pos = 0, vs_pos, ve_pos, dist_vs_pos, dist_ve_pos, prob_pos, lon_pos;
			vs_pos = str_buf.find(' ', begin_pos);
			ve_pos = str_buf.find(' ', vs_pos + 1);
			dist_vs_pos = str_buf.find(' ', ve_pos + 1);
			dist_ve_pos = str_buf.find(' ', dist_vs_pos + 1);
			prob_pos = str_buf.find(' ', dist_ve_pos + 1);
			lon_pos = str_buf.find(' ', prob_pos + 1);

			int refloc_id = atoi(str_buf.substr(begin_pos, vs_pos - begin_pos).c_str());
			int vs_id = atoi(str_buf.substr(vs_pos + 1, ve_pos - vs_pos - 1).c_str());
			int ve_id = atoi(str_buf.substr(ve_pos + 1, dist_vs_pos - ve_pos - 1).c_str());
			double dist_vs = static_cast<double>(atof(str_buf.substr(dist_vs_pos + 1, dist_ve_pos - dist_vs_pos - 1).c_str()));
			double dist_ve = static_cast<double>(atof(str_buf.substr(dist_ve_pos + 1, prob_pos - dist_ve_pos - 1).c_str()));
			double prob = static_cast<double>(atof(str_buf.substr(prob_pos + 1, lon_pos - prob_pos - 1).c_str()));
			// lon and lat are useless for network traversal

			// insert a reference location vertex to <vs, ve>
			vertex refloc_v(refloc_id, 'r');
			std::vector<directed_edge> removed_edges, inserted_edges;
			graph.insert_vertex(vertex(vs_id, 'v'), vertex(ve_id, 'v'), refloc_v, dist_vs, dist_ve, &removed_edges, &inserted_edges,
				false); // "false" means not to replace overlapped vertex for reference location, we will create a virtual vertex for it

			// traverse graph from the reference location by dijkstra algorithm
			extend_visitor.set_vs_ve(vs_id, ve_id, dist_vs, dist_ve); // the original starting and ending vertices of the reference location
			extend_visitor.set_prob(prob); // set the present probability of the reference location
			top_visitor.set_refloc(refloc_id, prob);
			refloc_loc_edges_hash_map.clear(); // must reset the assistant hash map for each new reference location
			if (vs_id == ve_id)
				top_visitor.set_overlap(vs_id); // reference location overlaps a vertex
			else
				top_visitor.set_overlap(-1); // reference location doesn't overlap a vertex
			graph.dijkstra(refloc_v, &top_visitor, &extend_visitor);

			// restore the graph by removing the inserted reference location vertex
			graph.restore_graph(refloc_v, removed_edges, inserted_edges);
		}
	}
}

void LNB_construct_LNT(bool is_to_bidirectional, const char* edges_file_path, const wh::facility_info_map& facility_info, const wh::reference_info_list &refloc_info, LNT_hash_map& LNT, vertex_nnd_hash_map& nnd_map, typed_directed_graph& graph, fac_hash_map& facs_map, std::map<int, std::set<std::pair<int, int>>>& refloc_LN_map, std::map<int, std::pair<int, double>>& refloc_info_map)
{

	// 对图进行初始化
	graph.set_to_bidirectional(is_to_bidirectional);
	graph.init_graph(edges_file_path);

	// 在图上面部署设施，并进行检查
	graph.deploy_facilities(facility_info, &facs_map);
	if (!graph.get_is_facilities_deployed()) // 检查图和设施的状态
		return;

	LNB_extend_visitor extend_visitor;
	loc_edges_hash_map refloc_loc_edges_hash_map; // an assistant hash map for local network edges
	extend_visitor.set_data_structure(&facs_map, &refloc_loc_edges_hash_map); // set data structures

	// create a top event visitor for LNB algorithm
	LNB_k_top_visitor top_visitor;
	top_visitor.set_data_structures(&LNT, &refloc_loc_edges_hash_map, &nnd_map,  &refloc_LN_map,&refloc_info_map); // set data structures

	// deal with each reference location
	for(auto i:refloc_info)
	{
		int refloc_id = std::get<0>(i);
		int vs_id = std::get<1>(i);
		int ve_id = std::get<2>(i);
		double dist_vs = std::get<3>(i);
		double dist_ve = std::get<4>(i);
		double prob = std::get<5>(i);
		// insert a reference location vertex to <vs, ve>
		vertex refloc_v(refloc_id, 'r');
		std::vector<directed_edge> removed_edges, inserted_edges;
		graph.insert_vertex(vertex(vs_id, 'v'), vertex(ve_id, 'v'), refloc_v, dist_vs, dist_ve, &removed_edges, &inserted_edges,
			false); // "false" means not to replace overlapped vertex for reference location, we will create a virtual vertex for it
		// traverse graph from the reference location by dijkstra algorithm
		extend_visitor.set_vs_ve(vs_id, ve_id, dist_vs, dist_ve); // the original starting and ending vertices of the reference location
		extend_visitor.set_prob(prob); // set the present probability of the reference location
		top_visitor.set_refloc(refloc_id, prob);
		refloc_loc_edges_hash_map.clear(); // must reset the assistant hash map for each new reference location
		if (vs_id == ve_id)
			top_visitor.set_overlap(vs_id); // reference location overlaps a vertex
		else
			top_visitor.set_overlap(-1); // reference location doesn't overlap a vertex
		graph.dijkstra(refloc_v, &top_visitor, &extend_visitor);

		// restore the graph by removing the inserted reference location vertex
		graph.restore_graph(refloc_v, removed_edges, inserted_edges);
	}
}
//--------------------------------------------------------------------------------
// LNB algorithm: query optimal candidate based on LNT
// remark: the candidates file format must be "cand_id vs_id ve_id dist_vs_cand dist_cand_ve lon lat";
//		   for simplicity, we use LNT as a non-const parameter, hence, in this function, be careful to use it, and DON'T change its value anytime
// note: if a candidate locates in a local network of a reference location, which has no nearest facility (namely isolate sub-grahp), we view its ERD as 0
// [re] candidate: the optimal candidate; default candidate object means opening candidates file fails
// [out] checked_num: the number of candidates actually checked
// [in] LNT: the constructed hash map as LNT
// [in] nnd_map; the constructed hash map for reference locations that overlap some vertices
// [in] graph: the constructed graph
// [in] facs_map: a hash map for storing facilities associated with the endpoints
// [in] cands_file_path: file path of candidates
// 参数说明：
//		candidate:最优的候选者，如果是默认的候选者则说明打开候选文件失败
//		checked_num:实际被检查的候选者数量
//		LNT：一个hash表
//		nnd_map：覆盖了一些顶点的参考位置的hash表
//		graph：图
//		facs_map：存储设施以及其终点的hash表
//		cands_file_path:candidate的文件路径
// 需要改变的：
//		LNT，graph，facs_map，cands_file_path
// 需要记录candidate的相关信息
// 可以用一个set存储

candidate LNB_query(int &checked_num, LNT_hash_map &LNT, const vertex_nnd_hash_map &nnd_map, const typed_directed_graph &graph,
					const fac_hash_map &facs_map, const char *cands_file_path)
{
	cand_max_fibonacci_heap max_heap; // max-heap ordered by ERD+ in LNT
	cand_info_hash_map hash_map; // hash map for information of candidates

	// construct a max-heap for candidates
	std::ifstream ifs_cands(cands_file_path); // read candidates file
	if (ifs_cands.is_open()) // candidates file exists
	{
		char buf[1024];
		while (ifs_cands.getline(buf, 1024))
		{
			std::string str_buf(buf);

			// the candidates file format must be "cand_id vs_id ve_id dist_vs_cand dist_cand_ve lon lat"
			std::string::size_type begin_pos = 0, vs_pos, ve_pos, dist_vs_pos, dist_ve_pos, lon_pos;
			vs_pos = str_buf.find(' ', begin_pos);
			ve_pos = str_buf.find(' ', vs_pos + 1);
			dist_vs_pos = str_buf.find(' ', ve_pos + 1);
			dist_ve_pos = str_buf.find(' ', dist_vs_pos + 1);
			lon_pos = str_buf.find(' ', dist_ve_pos + 1);

			int cand_id = atoi(str_buf.substr(begin_pos, vs_pos - begin_pos).c_str());
			int vs_id = atoi(str_buf.substr(vs_pos + 1, ve_pos - vs_pos - 1).c_str());
			int ve_id = atoi(str_buf.substr(ve_pos + 1, dist_vs_pos - ve_pos - 1).c_str());
			double dist_vs = static_cast<double>(atof(str_buf.substr(dist_vs_pos + 1, dist_ve_pos - dist_vs_pos - 1).c_str()));
			double dist_ve = static_cast<double>(atof(str_buf.substr(dist_ve_pos + 1, lon_pos - dist_ve_pos - 1).c_str()));
			// lon and lat are useless for query

			if (vs_id != ve_id) // candidate splits an edge
			{
				// here, we explicitly indicate "vs" and "ve"
				std::pair<int, int> vs_ve(vs_id, ve_id), // vs->ve
					ve_vs(ve_id, vs_id); // ve->vs, reverse direction

				// retrieve ERD+ of edge
				double ERD_u = 0.0f; // ERD+ for ordering candidates in max-heap
				LNT_hash_map::const_iterator iter_vs_ve = LNT.find(vs_ve); // vs->ve
				LNT_hash_map::const_iterator iter_ve_vs = LNT.find(ve_vs); // ve->vs
				if (iter_vs_ve != LNT.cend() && iter_ve_vs != LNT.cend()) // vs->ve & ve->vs are both valid
					ERD_u = iter_vs_ve->second.first + iter_ve_vs->second.first; // larger than upper
				else if (iter_vs_ve != LNT.cend()) // only vs->ve is valid
					ERD_u = iter_vs_ve->second.first;
				else if (iter_ve_vs != LNT.cend()) // only ve->vs is valid
					ERD_u = iter_ve_vs->second.first;
				else // neither are valid, ERD+ should be 0.0f
					continue; // no need to consider this candidate

				max_heap.push(candidate(cand_id, ERD_u)); // push each candidate
				hash_map[cand_id] = boost::make_tuple(iter_vs_ve, iter_ve_vs, dist_vs, dist_ve); // record information of each candidate
			}
			else // vs_id == ve_id, candidate overlaps a vertex
				 // NOTE: 1) facility cannot overlap the vertex, otherwise, candidate overlaps facility, which is strictly forbidden;
				 //			 hence, any network traversal cannot end at the vertex, thus considering only out-edges can avoid double counting,
				 //			 where candidate is viewed as an intermediate vertex in a path, namely as vs and ve for two different edges, for computing ERd;
				 //		  2) also, if traversal ends immediately before the vertex (i.e., r->f->c), candidate is outside local network and has no benefit;
				 //		  3) moreover, if a reference location splits an edge with candidate (the vertex) as one of the two endpoints,
				 //			 namely out-edge c->r->ve, then Rd of c must > nnd (Dd+), thus it has to consider the reverse direction
				 //		  4) conversely, only considering in-edges is not enough, the counter example is reference location overlaps the vertex,
				 //			 and for this reference location, there is only out-edge
				 //		  5) in the special case, where c overlaps v and some r(s) also overlap v, we compute ERD with the help of vertex_nnd_hash_map
				 //		1、设施位置不能覆盖这个顶点，否则候选设施覆盖了一个已经存在的设施，这是绝对禁止的，因此，任何网络遍历
				//			不能在顶点处停止，因此仅仅考虑出边可以避免双重计数，此时候选设施被视为一条路径中的插入点
				//			也就是说
				//		2、同样的，如果遍历在遇到点之前立刻终止，候选设施将在本地网络之外，不会有好处
			{
				double ERD = 0.0f; // 对于覆盖了一个顶点的候选设施，我们直接计算它的ERD

				std::map<int, double> min_dist;
				adjacent_edges_hash_map::const_iterator iter_vertex = graph.adjacent_edges.find(vertex(vs_id, 'v')); // the overlapped vertex
				
				// considering only out-edges is enough; hence, no need to consider in-edges
				// 现在这种情况下，可以考虑入边，因为它并未累加，而是寻找每个参考位置最大的距离减小量
				std::set<out_edge>::const_iterator iter_out_edge = iter_vertex->second.first.cbegin();
				for (; iter_out_edge != iter_vertex->second.first.cend(); ++iter_out_edge) //遍历每一条出边
												// 对每一条边查看覆盖它的参考位置。(这会有重复啊！！！)compute ERd for each out-edge
				{
					// fault-tolerant check in case out-vertex is a facility
					int out_v_id = iter_out_edge->ve.id;
					double dist_vs_ve = iter_out_edge->dist;
					if (iter_out_edge->ve.type != 'v') // 以防终点不是普通的顶点，一定是设施点。must be 'f'
					{
						fac_hash_map::const_iterator iter_fac = facs_map.find(out_v_id); // as facility exists, this iterator must not be end()
						if (iter_fac->second.get<VS_ID>() == vs_id)
							out_v_id = iter_fac->second.get<VE_ID>();
						else
							out_v_id = iter_fac->second.get<VS_ID>();
						dist_vs_ve = iter_fac->second.get<VS_DIST>() + iter_fac->second.get<VE_DIST>(); // edge distance
					}

					LNT_hash_map::const_iterator iter_vs_ve = LNT.find(std::make_pair(vs_id, out_v_id)); // vs->ve
					if (iter_vs_ve != LNT.cend()) // vs->ve takes effect on ERd
					{
						std::vector<ref_loc_entry>::const_iterator iter_entry = iter_vs_ve->second.second.cbegin();
						for (; iter_entry != iter_vs_ve->second.second.cend(); ++iter_entry) // 这是遍历每一条边上的参考位置 each reference location related to this out-edge
						{
							// 1) we view edge distance as d(c, ve), then d(c, ve) must > offset, thus offset has no effect
							// 2) c (say the overlapped vertex) has definite distance from r, hence d(r, vs) <= nnd, thus Rd is impossible < 0 (locates outside local network)
							double Rd = iter_entry->get<DDL>() + dist_vs_ve; // Dd- + d(c, ve) >= 0
							if (Rd > iter_entry->get<DDU>() || Rd < 0) // > Dd+, must consider reverse direction
								continue;
							else // c takes effect
							{
								//ERD += Rd * iter_entry->get<PROB>();
								//std::cout << "id: " << iter_entry->get<REFF>() << '\t';
								int r_id = iter_entry->get<REFF>();
								if (min_dist.find(r_id) == min_dist.end()) // 这个参考位置还未被记录
									min_dist[r_id] = Rd * iter_entry->get<PROB>();
								else // 如果这个参考位置已经被记录，则比较那一条路径带来最大的减小量，保留最大值
								{
									double d1 = min_dist[r_id];
									double d2 = Rd * iter_entry->get<PROB>();
									min_dist[r_id] = (d1 > d2 ? d1 : d2);
								}
							}
						}
					}
				}
				{
					// 处理入边的情形
					std::set<vertex>::iterator iter_in_vertex = iter_vertex->second.second.begin();
					for (; iter_in_vertex != iter_vertex->second.second.end(); iter_in_vertex++)
					{
						int in_v_id = iter_in_vertex->id;
						double dist_vs_ve = 0.0;
						if (iter_in_vertex->type != 'v') // 如果这条边被一个设施所分割了
						{
							fac_hash_map::const_iterator iter_fac = facs_map.find(in_v_id); // as facility exists, this iterator must not be end()
							if (iter_fac->second.get<VS_ID>() == vs_id)
								in_v_id = iter_fac->second.get<VE_ID>();
							else
								in_v_id = iter_fac->second.get<VS_ID>();
						}
						LNT_hash_map::const_iterator iter_vs_ve = LNT.find(std::make_pair(in_v_id, vs_id)); 
						if (iter_vs_ve != LNT.cend()) 
						{
							std::vector<ref_loc_entry>::const_iterator iter_entry = iter_vs_ve->second.second.cbegin();
							for (; iter_entry != iter_vs_ve->second.second.cend(); ++iter_entry) 
							{
								double Rd = iter_entry->get<DDL>() + dist_vs_ve; // Dd- + d(c, ve) >= 0
								if (Rd > iter_entry->get<DDU>() || Rd < 0) // > Dd+, must consider reverse direction
									continue;
								else // c takes effect
								{
									int r_id = iter_entry->get<REFF>();
									if (min_dist.find(r_id) == min_dist.end()) // 这个参考位置还未被记录
										min_dist[r_id] = Rd * iter_entry->get<PROB>();
									else // 如果这个参考位置已经被记录，则比较那一条路径带来最大的减小量，保留最大值
									{
										double d1 = min_dist[r_id];
										double d2 = Rd * iter_entry->get<PROB>();
										min_dist[r_id] = (d1 > d2 ? d1 : d2);
									}
								}
							}
						}
					}
				}
				//std::cout << "size: " << min_dist.size() << std::endl;
				for (auto i : min_dist) // 将所有顶点所能取得的最大减小量相加
					ERD = ERD + i.second;

				// fault-tolerant check in case the candidate overlaps a vertex, which is also overlapped by some reference location(s)
				unsigned out_edges_size = static_cast<unsigned>(iter_vertex->second.first.size());
				vertex_nnd_hash_map::const_iterator iter_nnd = nnd_map.find(vs_id);
				if (iter_nnd != nnd_map.cend()) // some reference location(s) overlaps the vertex
					ERD -= (out_edges_size - 1) * iter_nnd->second; //没有执行 ERD = ERD - size * accumulated nnd (minus all out-edges) + accumulated nnd (reserve one out-edge)

				max_heap.push(candidate(cand_id, ERD)); // push candidate and actual ERD
				hash_map[cand_id] = boost::make_tuple(LNT.cend(), LNT.cend(), 0.0f, 0.0f); // set overlap flags (i.e., LNT.cend() and 0.0f) for the candidate
			}
		}
	}
	else // opening candidates file fails
		return candidate();

	candidate ol(-1, 0.0f); // initialize optimal location
	checked_num = 0; // intialize
	while (!max_heap.empty())
	{
		// retrieve the top candidate in max-heap
		candidate top_c = max_heap.top();
#ifdef ALGO_TESTING
		algo_out_file << "ERD+: c" << top_c.id << ": " << top_c.ERD << '\n';
#endif

#ifndef ALGO_TESTING_NO_EARLY_STOPPING
		if (top_c.ERD < ol.ERD) // current ol candidate is the optimal location
			break;
#endif
		++checked_num; // need to check more candidates

		if (hash_map[top_c.id].get<VE_DIST>() != 0 && hash_map[top_c.id].get<VS_DIST>() != 0) // c splits an edge, but not overlaps a vertex, as overlapping has definite ERD
		{
			top_c.ERD = 0.0f; // prepare to accumulate actual ERD of this candidate

			// iteratively deal with two possible edges vs->ve and ve->vs
			LNT_hash_map::const_iterator iters[2] = { hash_map[top_c.id].get<ITER_VS_VE>(), hash_map[top_c.id].get<ITER_VE_VS>() };
			double dist_c_ve[2] = { hash_map[top_c.id].get<VE_DIST>(), hash_map[top_c.id].get<VS_DIST>() }; // for vs->ve, VE_DIST; for ve->vs, VS_DIST
			for (int i = 0; i < 2; ++i)
			{
				std::vector<ref_loc_entry>::const_iterator iter_entry, iter_entry_end; // use "const", as ITER_VS_VE and ITER_VE_VS are both const_iterator
				if (iters[i] != LNT.cend()) // vs->ve or ve->vs exists
				{
					// iterate all related reference locations
					iter_entry_end = iters[i]->second.second.cend();
					for (iter_entry = iters[i]->second.second.cbegin(); iter_entry != iter_entry_end; ++iter_entry)
					{
						// the case that offset > 0
						if (dist_c_ve[i] < iter_entry->get<OFFSET>()) // the condition that offset takes effect
						{
#ifdef ALGO_TESTING
							algo_out_file << iters[i]->first << ", d(ve) = " << dist_c_ve[i] << " < offset = " << iter_entry->get<OFFSET>() << '\n';
#endif

							// utilizing virtual candidate c', which is the mapping of c with respect to lc, to compute ERd
							double dist_v_c_ve = 2.0f * iter_entry->get<OFFSET>() - dist_c_ve[i]; // d(c', ve) = 2 * offset - d(c, ve)
							top_c.ERD += (iter_entry->get<DDL>() + dist_v_c_ve) * iter_entry->get<PROB>();
							continue;
						}

						double Rd = iter_entry->get<DDL>() + dist_c_ve[i]; // Dd- + d(c, ve)
						if (Rd <= 0) // c locates outside local network (<), or has no benefit (==)
							continue;
						else // Rd > 0
						{
							if (Rd > iter_entry->get<DDU>()) // > Dd+, must consider reverse direction
								continue;
							else // c takes effect
								top_c.ERD += Rd * iter_entry->get<PROB>();
						}
					}
				}
			}
		}

#ifdef ALGO_TESTING
		algo_out_file << "ERD: c" << top_c.id << ": " << top_c.ERD << '\n';
#endif
		// update ol, if necessary
		if (top_c.ERD > ol.ERD)
		{
			ol.id = top_c.id;
			ol.ERD = top_c.ERD;
		}

		max_heap.pop(); // pop the top vertex
	}

	return ol; // the optimal candidate
}

candidate LNB_query(int &checked_num, LNT_hash_map &LNT, const vertex_nnd_hash_map &nnd_map, const typed_directed_graph &graph,
					const fac_hash_map &facs_map, const char *cands_file_path,std::map<int,std::tuple<int,int,double,double>> & cands_map)
{
	cand_max_fibonacci_heap max_heap; // max-heap ordered by ERD+ in LNT
	cand_info_hash_map hash_map; // hash map for information of candidates

	if (!cands_map.empty())
	{
		for (auto iter_c = cands_map.begin(); iter_c != cands_map.end(); iter_c++)
		{
			int cand_id = iter_c->first;
			int vs_id = std::get<0>(iter_c->second);
			int ve_id = std::get<1>(iter_c->second);
			double dist_vs = std::get<2>(iter_c->second);
			double dist_ve = std::get<3>(iter_c->second);

			if (vs_id != ve_id) // 分割了一条边
			{
				// here, we explicitly indicate "vs" and "ve"
				std::pair<int, int> vs_ve(vs_id, ve_id), // vs->ve
					ve_vs(ve_id, vs_id); // ve->vs, reverse direction

				// retrieve ERD+ of edge
				double ERD_u = 0.0f; // ERD+ for ordering candidates in max-heap
				LNT_hash_map::const_iterator iter_vs_ve = LNT.find(vs_ve); // vs->ve
				LNT_hash_map::const_iterator iter_ve_vs = LNT.find(ve_vs); // ve->vs
				if (iter_vs_ve != LNT.cend() && iter_ve_vs != LNT.cend()) // vs->ve & ve->vs are both valid
					ERD_u = iter_vs_ve->second.first + iter_ve_vs->second.first; // larger than upper
				else if (iter_vs_ve != LNT.cend()) // only vs->ve is valid
					ERD_u = iter_vs_ve->second.first;
				else if (iter_ve_vs != LNT.cend()) // only ve->vs is valid
					ERD_u = iter_ve_vs->second.first;
				else // neither are valid, ERD+ should be 0.0f
					continue; // no need to consider this candidate

				max_heap.push(candidate(cand_id, ERD_u)); // push each candidate
				hash_map[cand_id] = boost::make_tuple(iter_vs_ve, iter_ve_vs, dist_vs, dist_ve); // record information of each candidate
			}
			else // vs_id == ve_id, candidate overlaps a vertex
			{
				double ERD = 0.0f; // 对于覆盖了一个顶点的候选设施，我们直接计算它的ERD

				std::map<int, double> min_dist;
				adjacent_edges_hash_map::const_iterator iter_vertex = graph.adjacent_edges.find(vertex(vs_id, 'v')); // the overlapped vertex
				
				// considering only out-edges is enough; hence, no need to consider in-edges
				// 现在这种情况下，可以考虑入边，因为它并未累加，而是寻找每个参考位置最大的距离减小量
				std::set<out_edge>::const_iterator iter_out_edge = iter_vertex->second.first.cbegin();
				for (; iter_out_edge != iter_vertex->second.first.cend(); ++iter_out_edge) //遍历每一条出边
												// 对每一条边查看覆盖它的参考位置。(这会有重复啊！！！)compute ERd for each out-edge
				{
					// fault-tolerant check in case out-vertex is a facility
					int out_v_id = iter_out_edge->ve.id;
					double dist_vs_ve = iter_out_edge->dist;
					if (iter_out_edge->ve.type != 'v') // 以防终点不是普通的顶点，一定是设施点。must be 'f'
					{
						fac_hash_map::const_iterator iter_fac = facs_map.find(out_v_id); // as facility exists, this iterator must not be end()
						if (iter_fac->second.get<VS_ID>() == vs_id)
							out_v_id = iter_fac->second.get<VE_ID>();
						else
							out_v_id = iter_fac->second.get<VS_ID>();
						dist_vs_ve = iter_fac->second.get<VS_DIST>() + iter_fac->second.get<VE_DIST>(); // edge distance
					}

					LNT_hash_map::const_iterator iter_vs_ve = LNT.find(std::make_pair(vs_id, out_v_id)); // vs->ve
					if (iter_vs_ve != LNT.cend()) // vs->ve takes effect on ERd
					{
						std::vector<ref_loc_entry>::const_iterator iter_entry = iter_vs_ve->second.second.cbegin();
						for (; iter_entry != iter_vs_ve->second.second.cend(); ++iter_entry) // 这是遍历每一条边上的参考位置 each reference location related to this out-edge
						{
							// 1) we view edge distance as d(c, ve), then d(c, ve) must > offset, thus offset has no effect
							// 2) c (say the overlapped vertex) has definite distance from r, hence d(r, vs) <= nnd, thus Rd is impossible < 0 (locates outside local network)
							double Rd = iter_entry->get<DDL>() + dist_vs_ve; // Dd- + d(c, ve) >= 0
							if (Rd > iter_entry->get<DDU>()|| Rd < 0) // > Dd+, must consider reverse direction
								continue;
							else // c takes effect
							{
								//ERD += Rd * iter_entry->get<PROB>();
								//std::cout << "id: " << iter_entry->get<REFF>() << '\t';
								int r_id = iter_entry->get<REFF>();
								if (min_dist.find(r_id) == min_dist.end()) // 这个参考位置还未被记录
									min_dist[r_id] = Rd * iter_entry->get<PROB>();
								else // 如果这个参考位置已经被记录，则比较那一条路径带来最大的减小量，保留最大值
								{
									double d1 = min_dist[r_id];
									double d2 = Rd * iter_entry->get<PROB>();
									min_dist[r_id] = (d1 > d2 ? d1 : d2);
								}
							}
						}
					}
				}
				{
					// 处理入边的情形
					std::set<vertex>::iterator iter_in_vertex = iter_vertex->second.second.begin();
					for (; iter_in_vertex != iter_vertex->second.second.end(); iter_in_vertex++)
					{
						int in_v_id = iter_in_vertex->id;
						double dist_vs_ve = 0.0;
						if (iter_in_vertex->type != 'v') // 如果这条边被一个设施所分割了
						{
							fac_hash_map::const_iterator iter_fac = facs_map.find(in_v_id); // as facility exists, this iterator must not be end()
							if (iter_fac->second.get<VS_ID>() == vs_id)
								in_v_id = iter_fac->second.get<VE_ID>();
							else
								in_v_id = iter_fac->second.get<VS_ID>();
						}
						LNT_hash_map::const_iterator iter_vs_ve = LNT.find(std::make_pair(in_v_id, vs_id)); 
						if (iter_vs_ve != LNT.cend()) 
						{
							std::vector<ref_loc_entry>::const_iterator iter_entry = iter_vs_ve->second.second.cbegin();
							for (; iter_entry != iter_vs_ve->second.second.cend(); ++iter_entry) 
							{
								double Rd = iter_entry->get<DDL>() + dist_vs_ve; // Dd- + d(c, ve) >= 0
								if (Rd > iter_entry->get<DDU>() || Rd < 0) // > Dd+, must consider reverse direction
									continue;
								else // c takes effect
								{
									int r_id = iter_entry->get<REFF>();
									if (min_dist.find(r_id) == min_dist.end()) // 这个参考位置还未被记录
										min_dist[r_id] = Rd * iter_entry->get<PROB>();
									else // 如果这个参考位置已经被记录，则比较那一条路径带来最大的减小量，保留最大值
									{
										double d1 = min_dist[r_id];
										double d2 = Rd * iter_entry->get<PROB>();
										min_dist[r_id] = (d1 > d2 ? d1 : d2);
									}
								}
							}
						}
					}
				}
				//std::cout << "size: " << min_dist.size() << std::endl;
				for (auto i : min_dist) // 将所有顶点所能取得的最大减小量相加
					ERD = ERD + i.second;

				// fault-tolerant check in case the candidate overlaps a vertex, which is also overlapped by some reference location(s)
				unsigned out_edges_size = static_cast<unsigned>(iter_vertex->second.first.size());
				vertex_nnd_hash_map::const_iterator iter_nnd = nnd_map.find(vs_id);
				if (iter_nnd != nnd_map.cend()) // some reference location(s) overlaps the vertex
					ERD -= (out_edges_size - 1) * iter_nnd->second; //没有执行 ERD = ERD - size * accumulated nnd (minus all out-edges) + accumulated nnd (reserve one out-edge)

				max_heap.push(candidate(cand_id, ERD)); // push candidate and actual ERD
				hash_map[cand_id] = boost::make_tuple(LNT.cend(), LNT.cend(), 0.0f, 0.0f); // set overlap flags (i.e., LNT.cend() and 0.0f) for the candidate
			}
		}
	}
	else
	{
		std::ifstream ifs_cands(cands_file_path); // read candidates file
		if (ifs_cands.is_open()) // candidates file exists
		{
			char buf[1024];
			while (ifs_cands.getline(buf, 1024))
			{
				std::string str_buf(buf);

				// the candidates file format must be "cand_id vs_id ve_id dist_vs_cand dist_cand_ve lon lat"
				std::string::size_type begin_pos = 0, vs_pos, ve_pos, dist_vs_pos, dist_ve_pos, lon_pos;
				vs_pos = str_buf.find(' ', begin_pos);
				ve_pos = str_buf.find(' ', vs_pos + 1);
				dist_vs_pos = str_buf.find(' ', ve_pos + 1);
				dist_ve_pos = str_buf.find(' ', dist_vs_pos + 1);
				lon_pos = str_buf.find(' ', dist_ve_pos + 1);

				int cand_id = atoi(str_buf.substr(begin_pos, vs_pos - begin_pos).c_str());
				int vs_id = atoi(str_buf.substr(vs_pos + 1, ve_pos - vs_pos - 1).c_str());
				int ve_id = atoi(str_buf.substr(ve_pos + 1, dist_vs_pos - ve_pos - 1).c_str());
				double dist_vs = static_cast<double>(atof(str_buf.substr(dist_vs_pos + 1, dist_ve_pos - dist_vs_pos - 1).c_str()));
				double dist_ve = static_cast<double>(atof(str_buf.substr(dist_ve_pos + 1, lon_pos - dist_ve_pos - 1).c_str()));
				cands_map[cand_id] = std::make_tuple(vs_id, ve_id, dist_vs, dist_ve); // 存储候选设施信息

				if (vs_id != ve_id) // candidate splits an edge
				{
					// here, we explicitly indicate "vs" and "ve"
					std::pair<int, int> vs_ve(vs_id, ve_id), // vs->ve
						ve_vs(ve_id, vs_id); // ve->vs, reverse direction

					// retrieve ERD+ of edge
					double ERD_u = 0.0f; // ERD+ for ordering candidates in max-heap
					LNT_hash_map::const_iterator iter_vs_ve = LNT.find(vs_ve); // vs->ve
					LNT_hash_map::const_iterator iter_ve_vs = LNT.find(ve_vs); // ve->vs
					if (iter_vs_ve != LNT.cend() && iter_ve_vs != LNT.cend()) // vs->ve & ve->vs are both valid
						ERD_u = iter_vs_ve->second.first + iter_ve_vs->second.first; // larger than upper
					else if (iter_vs_ve != LNT.cend()) // only vs->ve is valid
						ERD_u = iter_vs_ve->second.first;
					else if (iter_ve_vs != LNT.cend()) // only ve->vs is valid
						ERD_u = iter_ve_vs->second.first;
					else // neither are valid, ERD+ should be 0.0f
						continue; // no need to consider this candidate

					max_heap.push(candidate(cand_id, ERD_u)); // push each candidate
					hash_map[cand_id] = boost::make_tuple(iter_vs_ve, iter_ve_vs, dist_vs, dist_ve); // record information of each candidate
				}
				else // vs_id == ve_id, candidate overlaps a vertex
					 // NOTE: 1) facility cannot overlap the vertex, otherwise, candidate overlaps facility, which is strictly forbidden;
					 //			 hence, any network traversal cannot end at the vertex, thus considering only out-edges can avoid double counting,
					 //			 where candidate is viewed as an intermediate vertex in a path, namely as vs and ve for two different edges, for computing ERd;
					 //		  2) also, if traversal ends immediately before the vertex (i.e., r->f->c), candidate is outside local network and has no benefit;
					 //		  3) moreover, if a reference location splits an edge with candidate (the vertex) as one of the two endpoints,
					 //			 namely out-edge c->r->ve, then Rd of c must > nnd (Dd+), thus it has to consider the reverse direction
					 //		  4) conversely, only considering in-edges is not enough, the counter example is reference location overlaps the vertex,
					 //			 and for this reference location, there is only out-edge
					 //		  5) in the special case, where c overlaps v and some r(s) also overlap v, we compute ERD with the help of vertex_nnd_hash_map
					 //		1、设施位置不能覆盖这个顶点，否则候选设施覆盖了一个已经存在的设施，这是绝对禁止的，因此，任何网络遍历
					//			不能在顶点处停止，因此仅仅考虑出边可以避免双重计数，此时候选设施被视为一条路径中的插入点
					//			也就是说
					//		2、同样的，如果遍历在遇到点之前立刻终止，候选设施将在本地网络之外，不会有好处
				{
					double ERD = 0.0f; // 对于覆盖了一个顶点的候选设施，我们直接计算它的ERD

					std::map<int, double> min_dist;
					adjacent_edges_hash_map::const_iterator iter_vertex = graph.adjacent_edges.find(vertex(vs_id, 'v')); // the overlapped vertex

					// considering only out-edges is enough; hence, no need to consider in-edges
					// 现在这种情况下，可以考虑入边，因为它并未累加，而是寻找每个参考位置最大的距离减小量
					std::set<out_edge>::const_iterator iter_out_edge = iter_vertex->second.first.cbegin();
					for (; iter_out_edge != iter_vertex->second.first.cend(); ++iter_out_edge) //遍历每一条出边
													// 对每一条边查看覆盖它的参考位置。(这会有重复啊！！！)compute ERd for each out-edge
					{
						// fault-tolerant check in case out-vertex is a facility
						int out_v_id = iter_out_edge->ve.id;
						double dist_vs_ve = iter_out_edge->dist;
						if (iter_out_edge->ve.type != 'v') // 以防终点不是普通的顶点，一定是设施点。must be 'f'
						{
							fac_hash_map::const_iterator iter_fac = facs_map.find(out_v_id); // as facility exists, this iterator must not be end()
							if (iter_fac->second.get<VS_ID>() == vs_id)
								out_v_id = iter_fac->second.get<VE_ID>();
							else
								out_v_id = iter_fac->second.get<VS_ID>();
							dist_vs_ve = iter_fac->second.get<VS_DIST>() + iter_fac->second.get<VE_DIST>(); // edge distance
						}

						LNT_hash_map::const_iterator iter_vs_ve = LNT.find(std::make_pair(vs_id, out_v_id)); // vs->ve
						if (iter_vs_ve != LNT.cend()) // vs->ve takes effect on ERd
						{
							std::vector<ref_loc_entry>::const_iterator iter_entry = iter_vs_ve->second.second.cbegin();
							for (; iter_entry != iter_vs_ve->second.second.cend(); ++iter_entry) // 这是遍历每一条边上的参考位置 each reference location related to this out-edge
							{
								// 1) we view edge distance as d(c, ve), then d(c, ve) must > offset, thus offset has no effect
								// 2) c (say the overlapped vertex) has definite distance from r, hence d(r, vs) <= nnd, thus Rd is impossible < 0 (locates outside local network)
								double Rd = iter_entry->get<DDL>() + dist_vs_ve; // Dd- + d(c, ve) >= 0
								if (Rd > iter_entry->get<DDU>() || Rd < 0) // > Dd+, must consider reverse direction
									continue;
								else // c takes effect
								{
									//ERD += Rd * iter_entry->get<PROB>();
									//std::cout << "id: " << iter_entry->get<REFF>() << '\t';
									int r_id = iter_entry->get<REFF>();
									if (min_dist.find(r_id) == min_dist.end()) // 这个参考位置还未被记录
										min_dist[r_id] = Rd * iter_entry->get<PROB>();
									else // 如果这个参考位置已经被记录，则比较那一条路径带来最大的减小量，保留最大值
									{
										double d1 = min_dist[r_id];
										double d2 = Rd * iter_entry->get<PROB>();
										min_dist[r_id] = (d1 > d2 ? d1 : d2);
									}
								}
							}
						}
					}
					{
						// 处理入边的情形
						std::set<vertex>::iterator iter_in_vertex = iter_vertex->second.second.begin();
						for (; iter_in_vertex != iter_vertex->second.second.end(); iter_in_vertex++)
						{
							int in_v_id = iter_in_vertex->id;
							double dist_vs_ve = 0.0;
							if (iter_in_vertex->type != 'v') // 如果这条边被一个设施所分割了
							{
								fac_hash_map::const_iterator iter_fac = facs_map.find(in_v_id); // as facility exists, this iterator must not be end()
								if (iter_fac->second.get<VS_ID>() == vs_id)
									in_v_id = iter_fac->second.get<VE_ID>();
								else
									in_v_id = iter_fac->second.get<VS_ID>();
							}
							LNT_hash_map::const_iterator iter_vs_ve = LNT.find(std::make_pair(in_v_id, vs_id));
							if (iter_vs_ve != LNT.cend())
							{
								std::vector<ref_loc_entry>::const_iterator iter_entry = iter_vs_ve->second.second.cbegin();
								for (; iter_entry != iter_vs_ve->second.second.cend(); ++iter_entry)
								{
									double Rd = iter_entry->get<DDL>() + dist_vs_ve; // Dd- + d(c, ve) >= 0
									if (Rd > iter_entry->get<DDU>() || Rd < 0) // > Dd+, must consider reverse direction
										continue;
									else // c takes effect
									{
										int r_id = iter_entry->get<REFF>();
										if (min_dist.find(r_id) == min_dist.end()) // 这个参考位置还未被记录
											min_dist[r_id] = Rd * iter_entry->get<PROB>();
										else // 如果这个参考位置已经被记录，则比较那一条路径带来最大的减小量，保留最大值
										{
											double d1 = min_dist[r_id];
											double d2 = Rd * iter_entry->get<PROB>();
											min_dist[r_id] = (d1 > d2 ? d1 : d2);
										}
									}
								}
							}
						}
					}
					//std::cout << "size: " << min_dist.size() << std::endl;
					for (auto i : min_dist) // 将所有顶点所能取得的最大减小量相加
						ERD = ERD + i.second;

					// fault-tolerant check in case the candidate overlaps a vertex, which is also overlapped by some reference location(s)
					unsigned out_edges_size = static_cast<unsigned>(iter_vertex->second.first.size());
					vertex_nnd_hash_map::const_iterator iter_nnd = nnd_map.find(vs_id);
					if (iter_nnd != nnd_map.cend()) // some reference location(s) overlaps the vertex
						ERD -= (out_edges_size - 1) * iter_nnd->second; //没有执行 ERD = ERD - size * accumulated nnd (minus all out-edges) + accumulated nnd (reserve one out-edge)

					max_heap.push(candidate(cand_id, ERD)); // push candidate and actual ERD
					hash_map[cand_id] = boost::make_tuple(LNT.cend(), LNT.cend(), 0.0f, 0.0f); // set overlap flags (i.e., LNT.cend() and 0.0f) for the candidate
				}
			}
		}
		else // opening candidates file fails
			return candidate();
	}

	candidate ol(-1, 0.0); // initialize optimal location
	checked_num = 0; // intialize
	while (!max_heap.empty())
	{
		// retrieve the top candidate in max-heap
		candidate top_c = max_heap.top();
#ifdef ALGO_TESTING
		algo_out_file << "ERD+: c" << top_c.id << ": " << top_c.ERD << '\n';
#endif

#ifndef ALGO_TESTING_NO_EARLY_STOPPING
		if (top_c.ERD < ol.ERD) // current ol candidate is the optimal location
			break;
#endif
		++checked_num; // need to check more candidates

		if (hash_map[top_c.id].get<VE_DIST>() != 0 && hash_map[top_c.id].get<VS_DIST>() != 0) // c splits an edge, but not overlaps a vertex, as overlapping has definite ERD
		{
			top_c.ERD = 0.0f; // prepare to accumulate actual ERD of this candidate

			// iteratively deal with two possible edges vs->ve and ve->vs
			LNT_hash_map::const_iterator iters[2] = { hash_map[top_c.id].get<ITER_VS_VE>(), hash_map[top_c.id].get<ITER_VE_VS>() };
			double dist_c_ve[2] = { hash_map[top_c.id].get<VE_DIST>(), hash_map[top_c.id].get<VS_DIST>() }; // for vs->ve, VE_DIST; for ve->vs, VS_DIST
			for (int i = 0; i < 2; ++i)
			{
				std::vector<ref_loc_entry>::const_iterator iter_entry, iter_entry_end; // use "const", as ITER_VS_VE and ITER_VE_VS are both const_iterator
				if (iters[i] != LNT.cend()) // vs->ve or ve->vs exists
				{
					// 遍历所有的参考位置
					iter_entry_end = iters[i]->second.second.cend();
					for (iter_entry = iters[i]->second.second.cbegin(); iter_entry != iter_entry_end; ++iter_entry)
					{
						// the case that offset > 0
#ifdef WH_TEST
				//		std::cout << "id: " << iter_entry->get<REFF>() << " Dd+: " << iter_entry->get<DDU>()
				//			<< " DD-: " << iter_entry->get<DDL>()<< std::endl;
#endif
						int idd = iter_entry->get<REFF>();
						double pRob = iter_entry->get<PROB>();
						if (dist_c_ve[i] < iter_entry->get<OFFSET>()) // the condition that offset takes effect
						{
#ifdef ALGO_TESTING
							algo_out_file << iters[i]->first << ", d(ve) = " << dist_c_ve[i] << " < offset = " << iter_entry->get<OFFSET>() << '\n';
#endif

							// utilizing virtual candidate c', which is the mapping of c with respect to lc, to compute ERd
							double dist_v_c_ve = 2.0f * iter_entry->get<OFFSET>() - dist_c_ve[i]; // d(c', ve) = 2 * offset - d(c, ve)
							top_c.ERD += (iter_entry->get<DDL>() + dist_v_c_ve) * iter_entry->get<PROB>();
							continue;
						}

						double Rd = iter_entry->get<DDL>() + dist_c_ve[i]; // Dd- + d(c, ve)
						if (Rd <= 0) // c locates outside local network (<), or has no benefit (==)
							continue;
						else // Rd > 0
						{
							if (Rd > iter_entry->get<DDU>()) // > Dd+, must consider reverse direction
								continue;
							else // c takes effect
								top_c.ERD += Rd * iter_entry->get<PROB>();
						}
					}
				}
			}
		}

#ifdef ALGO_TESTING
		algo_out_file << "ERD: c" << top_c.id << ": " << top_c.ERD << '\n';
#endif
		// update ol, if necessary
		if (top_c.ERD > ol.ERD)
		{
			ol.id = top_c.id;
			ol.ERD = top_c.ERD;
		}

		max_heap.pop(); // pop the top vertex
	}

	return ol; // the optimal candidate
}

candidate LNB_query(int& checked_num, LNT_hash_map& LNT, const vertex_nnd_hash_map& nnd_map, const typed_directed_graph& graph,
	const fac_hash_map& facs_map, wh::candidate_info_map& candidate_info)
{
	cand_max_fibonacci_heap max_heap; // max-heap ordered by ERD+ in LNT
	cand_info_hash_map hash_map; // hash map for information of candidates

	if (!candidate_info.empty())
	{
		for (auto iter_c = candidate_info.begin(); iter_c != candidate_info.end(); iter_c++)
		{
			int cand_id = iter_c->first;
			int vs_id = std::get<0>(iter_c->second);
			int ve_id = std::get<1>(iter_c->second);
			double dist_vs = std::get<2>(iter_c->second);
			double dist_ve = std::get<3>(iter_c->second);

			if (vs_id != ve_id) // 分割了一条边
			{
				// here, we explicitly indicate "vs" and "ve"
				std::pair<int, int> vs_ve(vs_id, ve_id), // vs->ve
					ve_vs(ve_id, vs_id); // ve->vs, reverse direction

				// retrieve ERD+ of edge
				double ERD_u = 0.0f; // ERD+ for ordering candidates in max-heap
				LNT_hash_map::const_iterator iter_vs_ve = LNT.find(vs_ve); // vs->ve
				LNT_hash_map::const_iterator iter_ve_vs = LNT.find(ve_vs); // ve->vs
				if (iter_vs_ve != LNT.cend() && iter_ve_vs != LNT.cend()) // vs->ve & ve->vs are both valid
					ERD_u = iter_vs_ve->second.first + iter_ve_vs->second.first; // larger than upper
				else if (iter_vs_ve != LNT.cend()) // only vs->ve is valid
					ERD_u = iter_vs_ve->second.first;
				else if (iter_ve_vs != LNT.cend()) // only ve->vs is valid
					ERD_u = iter_ve_vs->second.first;
				else // neither are valid, ERD+ should be 0.0f
					continue; // no need to consider this candidate

				max_heap.push(candidate(cand_id, ERD_u)); // push each candidate
				hash_map[cand_id] = boost::make_tuple(iter_vs_ve, iter_ve_vs, dist_vs, dist_ve); // record information of each candidate
			}
			else // vs_id == ve_id, candidate overlaps a vertex
			{
				double ERD = 0.0f; // 对于覆盖了一个顶点的候选设施，我们直接计算它的ERD

				std::map<int, double> min_dist;
				adjacent_edges_hash_map::const_iterator iter_vertex = graph.adjacent_edges.find(vertex(vs_id, 'v')); // the overlapped vertex
				
				// considering only out-edges is enough; hence, no need to consider in-edges
				// 现在这种情况下，可以考虑入边，因为它并未累加，而是寻找每个参考位置最大的距离减小量
				std::set<out_edge>::const_iterator iter_out_edge = iter_vertex->second.first.cbegin();
				for (; iter_out_edge != iter_vertex->second.first.cend(); ++iter_out_edge) //遍历每一条出边
												// 对每一条边查看覆盖它的参考位置。(这会有重复啊！！！)compute ERd for each out-edge
				{
					// fault-tolerant check in case out-vertex is a facility
					int out_v_id = iter_out_edge->ve.id;
					double dist_vs_ve = iter_out_edge->dist;
					if (iter_out_edge->ve.type != 'v') // 以防终点不是普通的顶点，一定是设施点。must be 'f'
					{
						fac_hash_map::const_iterator iter_fac = facs_map.find(out_v_id); // as facility exists, this iterator must not be end()
						if (iter_fac->second.get<VS_ID>() == vs_id)
							out_v_id = iter_fac->second.get<VE_ID>();
						else
							out_v_id = iter_fac->second.get<VS_ID>();
						dist_vs_ve = iter_fac->second.get<VS_DIST>() + iter_fac->second.get<VE_DIST>(); // edge distance
					}

					LNT_hash_map::const_iterator iter_vs_ve = LNT.find(std::make_pair(vs_id, out_v_id)); // vs->ve
					if (iter_vs_ve != LNT.cend()) // vs->ve takes effect on ERd
					{
						std::vector<ref_loc_entry>::const_iterator iter_entry = iter_vs_ve->second.second.cbegin();
						for (; iter_entry != iter_vs_ve->second.second.cend(); ++iter_entry) // 这是遍历每一条边上的参考位置 each reference location related to this out-edge
						{
							// 1) we view edge distance as d(c, ve), then d(c, ve) must > offset, thus offset has no effect
							// 2) c (say the overlapped vertex) has definite distance from r, hence d(r, vs) <= nnd, thus Rd is impossible < 0 (locates outside local network)
							double Rd = iter_entry->get<DDL>() + dist_vs_ve; // Dd- + d(c, ve) >= 0
							if (Rd > iter_entry->get<DDU>() || Rd < 0) // > Dd+, must consider reverse direction
								continue;
							else // c takes effect
							{
								//ERD += Rd * iter_entry->get<PROB>();
								//std::cout << "id: " << iter_entry->get<REFF>() << '\t';
								int r_id = iter_entry->get<REFF>();
								if (min_dist.find(r_id) == min_dist.end()) // 这个参考位置还未被记录
									min_dist[r_id] = Rd * iter_entry->get<PROB>();
								else // 如果这个参考位置已经被记录，则比较那一条路径带来最大的减小量，保留最大值
								{
									double d1 = min_dist[r_id];
									double d2 = Rd * iter_entry->get<PROB>();
									min_dist[r_id] = (d1 > d2 ? d1 : d2);
								}
							}
						}
					}
				}
				{
					// 处理入边的情形
					std::set<vertex>::iterator iter_in_vertex = iter_vertex->second.second.begin();
					for (; iter_in_vertex != iter_vertex->second.second.end(); iter_in_vertex++)
					{
						int in_v_id = iter_in_vertex->id;
						double dist_vs_ve = 0.0;
						if (iter_in_vertex->type != 'v') // 如果这条边被一个设施所分割了
						{
							fac_hash_map::const_iterator iter_fac = facs_map.find(in_v_id); // as facility exists, this iterator must not be end()
							if (iter_fac->second.get<VS_ID>() == vs_id)
								in_v_id = iter_fac->second.get<VE_ID>();
							else
								in_v_id = iter_fac->second.get<VS_ID>();
						}

						LNT_hash_map::const_iterator iter_vs_ve = LNT.find(std::make_pair(in_v_id, vs_id)); 
						if (iter_vs_ve != LNT.cend()) 
						{
							std::vector<ref_loc_entry>::const_iterator iter_entry = iter_vs_ve->second.second.cbegin();
							for (; iter_entry != iter_vs_ve->second.second.cend(); ++iter_entry) 
							{
								double Rd = iter_entry->get<DDL>() + dist_vs_ve; // Dd- + d(c, ve) >= 0
								if (Rd > iter_entry->get<DDU>() || Rd < 0) // > Dd+, must consider reverse direction
									continue;
								else // c takes effect
								{
									int r_id = iter_entry->get<REFF>();
									if (min_dist.find(r_id) == min_dist.end()) // 这个参考位置还未被记录
										min_dist[r_id] = Rd * iter_entry->get<PROB>();
									else // 如果这个参考位置已经被记录，则比较那一条路径带来最大的减小量，保留最大值
									{
										double d1 = min_dist[r_id];
										double d2 = Rd * iter_entry->get<PROB>();
										min_dist[r_id] = (d1 > d2 ? d1 : d2);
									}
								}
							}
						}
					}
				}
				//std::cout << "size: " << min_dist.size() << std::endl;
				for (auto i : min_dist) // 将所有顶点所能取得的最大减小量相加
					ERD = ERD + i.second;

				// fault-tolerant check in case the candidate overlaps a vertex, which is also overlapped by some reference location(s)
				unsigned out_edges_size = static_cast<unsigned>(iter_vertex->second.first.size());
				vertex_nnd_hash_map::const_iterator iter_nnd = nnd_map.find(vs_id);
				if (iter_nnd != nnd_map.cend()) // some reference location(s) overlaps the vertex
					ERD -= (out_edges_size - 1) * iter_nnd->second; //没有执行 ERD = ERD - size * accumulated nnd (minus all out-edges) + accumulated nnd (reserve one out-edge)

				max_heap.push(candidate(cand_id, ERD)); // push candidate and actual ERD
				hash_map[cand_id] = boost::make_tuple(LNT.cend(), LNT.cend(), 0.0f, 0.0f); // set overlap flags (i.e., LNT.cend() and 0.0f) for the candidate
			}
		}
	}

	candidate ol(-1, 0.0); // initialize optimal location
	checked_num = 0; // intialize
	while (!max_heap.empty())
	{
		// retrieve the top candidate in max-heap
		candidate top_c = max_heap.top();
#ifdef ALGO_TESTING
		algo_out_file << "ERD+: c" << top_c.id << ": " << top_c.ERD << '\n';
#endif

#ifndef ALGO_TESTING_NO_EARLY_STOPPING
		if (top_c.ERD < ol.ERD) // current ol candidate is the optimal location
			break;
#endif
		++checked_num; // need to check more candidates

		if (hash_map[top_c.id].get<VE_DIST>() != 0 && hash_map[top_c.id].get<VS_DIST>() != 0) // c splits an edge, but not overlaps a vertex, as overlapping has definite ERD
		{
			top_c.ERD = 0.0f; // prepare to accumulate actual ERD of this candidate

			// iteratively deal with two possible edges vs->ve and ve->vs
			LNT_hash_map::const_iterator iters[2] = { hash_map[top_c.id].get<ITER_VS_VE>(), hash_map[top_c.id].get<ITER_VE_VS>() };
			double dist_c_ve[2] = { hash_map[top_c.id].get<VE_DIST>(), hash_map[top_c.id].get<VS_DIST>() }; // for vs->ve, VE_DIST; for ve->vs, VS_DIST
			for (int i = 0; i < 2; ++i)
			{
				std::vector<ref_loc_entry>::const_iterator iter_entry, iter_entry_end; // use "const", as ITER_VS_VE and ITER_VE_VS are both const_iterator
				if (iters[i] != LNT.cend()) // vs->ve or ve->vs exists
				{
					// 遍历所有的参考位置
					iter_entry_end = iters[i]->second.second.cend();
					for (iter_entry = iters[i]->second.second.cbegin(); iter_entry != iter_entry_end; ++iter_entry)
					{
						// the case that offset > 0
#ifdef WH_TEST
			//			std::cout << "id: " << iter_entry->get<REFF>() << " Dd+: " << iter_entry->get<DDU>()
			//				<< " DD-: " << iter_entry->get<DDL>()<< std::endl;
#endif
						int idd = iter_entry->get<REFF>();
						double pRob = iter_entry->get<PROB>();
						if (dist_c_ve[i] < iter_entry->get<OFFSET>()) // the condition that offset takes effect
						{
#ifdef ALGO_TESTING
							algo_out_file << iters[i]->first << ", d(ve) = " << dist_c_ve[i] << " < offset = " << iter_entry->get<OFFSET>() << '\n';
#endif

							// utilizing virtual candidate c', which is the mapping of c with respect to lc, to compute ERd
							double dist_v_c_ve = 2.0f * iter_entry->get<OFFSET>() - dist_c_ve[i]; // d(c', ve) = 2 * offset - d(c, ve)
							top_c.ERD += (iter_entry->get<DDL>() + dist_v_c_ve) * iter_entry->get<PROB>();
							continue;
						}

						double Rd = iter_entry->get<DDL>() + dist_c_ve[i]; // Dd- + d(c, ve)
						if (Rd <= 0) // c locates outside local network (<), or has no benefit (==)
							continue;
						else // Rd > 0
						{
							if (Rd > iter_entry->get<DDU>()) // > Dd+, must consider reverse direction
								continue;
							else // c takes effect
								top_c.ERD += Rd * iter_entry->get<PROB>();
						}
					}
				}
			}
		}

#ifdef ALGO_TESTING
		algo_out_file << "ERD: c" << top_c.id << ": " << top_c.ERD << '\n';
#endif
		// update ol, if necessary
		if (top_c.ERD > ol.ERD)
		{
			ol.id = top_c.id;
			ol.ERD = top_c.ERD;
		}

		max_heap.pop(); // pop the top vertex
	}

	return ol; // the optimal candidate
}

void LNB_update_LNT(const candidate & ol, LNT_hash_map & LNT, typed_directed_graph & graph, fac_hash_map & facs_map, std::map<int, std::set<std::pair<int, int>>> & refloc_LN_map, wh::candidate_info_map& cands_map, const char * reflocs_file_path, std::map<int,std::pair<int,double>> & refloc_info_map)
{
	std::tuple<int, int, double, double> op_c = cands_map[ol.id];	//	最优候选位置的vs_id, ve_id, vs_dist, ve_dist
	int vs_id = std::get<0>(op_c);
	int ve_id = std::get<1>(op_c);
	double vs_dist = std::get<2>(op_c);
	double ve_dist = std::get<3>(op_c);
	std::set<std::pair<int, int>> need_deal_with_edge; // 用来记录需要处理的边

	//从cands_map中删除该候选位置记录，并且将新的设施位置插入到图和facs_map中
	cands_map.erase(ol.id);
	int new_fac_id = ol.id + 10000;
	graph.insert_vertex(vertex(vs_id, 'v'), vertex(ve_id, 'v'), vertex(new_fac_id, 'f'), vs_dist, ve_dist);
	facs_map[new_fac_id] = boost::make_tuple(vs_id, ve_id, vs_dist, ve_dist);

	// 记录需要处理的边
	if (vs_id != ve_id) // 如果该参考位置分割了一条边，只需处理一条边
		need_deal_with_edge.insert(std::make_pair(vs_id, ve_id));
	else // 否则所有涉及的边都要处理
	{
		auto iter = graph.adjacent_edges.find(vertex(vs_id, 'v')); // 找到该顶点
		for (auto i : iter->second.first)
			need_deal_with_edge.insert(std::make_pair(vs_id, i.ve.id)); // 记录所有的出边
		for (auto i : iter->second.second)
			need_deal_with_edge.insert(std::make_pair(vs_id, i.id)); // 记录入边
	}

	// 下面开始进行相关的处理
	for (auto e : need_deal_with_edge)
	{
		std::pair<int, int> vs_ve = e;
		std::pair<int, int> ve_vs = std::make_pair(e.second, e.first);
		std::set<int> cover_c_rd;	// 记录那些LN覆盖了c的参考位置id
		bool is_from_vs_to_ve = true;

		LNT_hash_map::iterator iter_vs_ve = LNT.find(vs_ve);
		while (true)
		{
			if (iter_vs_ve != LNT.end())
			{
				boost::unordered_map<int, double> refloc_Rd_map;	// 参考位置的id以及插入c后，距离最近设施的距离

				// 以下for循环找到所有受到影响的参考位置id
				std::vector<ref_loc_entry>::iterator iter_ref_loc_entry = iter_vs_ve->second.second.begin();
				std::vector<ref_loc_entry>::iterator iter_ref_loc_entry_end = iter_vs_ve->second.second.end();
				double e_dist = vs_dist; // 默认为 vs_dist，即当 is_from_vs_to_ve 为假时，ve->vs，此时 VE 是 vs
				if (is_from_vs_to_ve) // 如果为真，即是 vs->ve ，此时 VE 是ve
					e_dist = ve_dist;
				for (; iter_ref_loc_entry != iter_ref_loc_entry_end; iter_ref_loc_entry++)
				{
					int r_id = iter_ref_loc_entry->get<REFF>(); // 取得参考位置id
					if (is_from_vs_to_ve)
						cover_c_rd.insert(r_id);
					else
						if (cover_c_rd.find(r_id) != cover_c_rd.end())	// 如果这个参考位置已经被记录了
							continue;

					if (e_dist < iter_ref_loc_entry->get<OFFSET>())
					{
						double dist_v_c_ve = 2.0f * iter_ref_loc_entry->get<OFFSET>() - e_dist; // d(c', ve) = 2 * offset - d(c, ve)
						refloc_Rd_map[r_id] = (iter_ref_loc_entry->get<DDL>() + dist_v_c_ve);
					}
					else
					{
						double ddl = iter_ref_loc_entry->get<DDL>();
						double Rd = iter_ref_loc_entry->get<DDL>() + e_dist;	// Rd 代表最近距离改变量
						if (Rd > iter_ref_loc_entry->get<DDU>())
						{
							if (is_from_vs_to_ve)	// 如果是第一次，将参考位置id从受影响的参考位置集合中删除，否则不采取任何动作（因为在第二次时并没有将其插入）
								cover_c_rd.erase(r_id);
							continue;
						}
						else if (Rd > 0)
							refloc_Rd_map[r_id] = Rd;
					}

				}


				// 下面的for循环，处理每一个受影响的参考位置 注意：没有用到上面的 cover_c_rd!!!!!!
				for (boost::unordered_map<int, double>::iterator iter_r_Rd = refloc_Rd_map.begin(); iter_r_Rd != refloc_Rd_map.end(); iter_r_Rd++)
				{
					int the_refloc = iter_r_Rd->first; // 当前被处理的参考位置id
					double Rd = iter_r_Rd->second;	// 距离相应最近设施的距离

					// 下面的for循环判断其LN中的每一条边
					std::set<std::pair<int, int>> need_to_delete_from_LN;
					std::set<std::pair<int, int>>::iterator iter_LN = refloc_LN_map[the_refloc].begin(), iter_LN_end = refloc_LN_map[the_refloc].end();
					for (; iter_LN != iter_LN_end; iter_LN++)
					{
						// 对其中的每一条边我们遍历LNT，找到该参考位置
						std::vector<ref_loc_entry>::iterator iter_LN_r = LNT[*iter_LN].second.begin(), iter_LN_r_end = LNT[*iter_LN].second.end();
						for (; iter_LN_r != iter_LN_r_end; iter_LN_r++)
						{
							if (iter_LN_r->get<REFF>() == the_refloc)
							{
								double dist_min_change = refloc_info_map[the_refloc].second - Rd;////////////////////////////////////
								double Dd_u = iter_LN_r->get<DDU>() - Rd;	// 新的上限
								if (Dd_u <= 0)	// 如果新的上限小于0,说明该边要从LN中移除
								{
									LNT[*iter_LN].first -= iter_LN_r->get<DDU>() * iter_LN_r->get<PROB>();	// 该边所能取得的最大值变小
									LNT[*iter_LN].second.erase(iter_LN_r);
									need_to_delete_from_LN.insert(*iter_LN);
								}
								else
								{
									LNT[*iter_LN].first -= iter_LN_r->get<DDU>() * iter_LN_r->get<PROB>();
									iter_LN_r->get<DDU>() = Dd_u;
									LNT[*iter_LN].first += iter_LN_r->get<DDU>() * iter_LN_r->get<PROB>();
									iter_LN_r->get<DDL>() -= Rd;	// Rd并没有×概率
								}
								break;
							}
						}
					}
					for (auto iter_remove = need_to_delete_from_LN.begin(); iter_remove != need_to_delete_from_LN.end(); iter_remove++)
						refloc_LN_map[the_refloc].erase(*iter_remove);
					refloc_info_map[the_refloc] = std::make_pair(new_fac_id, refloc_info_map[the_refloc].second - Rd);
				}
			}

			if (is_from_vs_to_ve) // 第一次执行时的边是<vs, ve> ，第二次执行边变为了<ve, vs> 
			{
				is_from_vs_to_ve = false;
				iter_vs_ve = LNT.find(ve_vs);
			}
			else
				break;
		}
	}
}
